///////////////////////////////////////////////////////////////////////////////
// Name:        prune_subwindows.cpp
// Purpose:     Prune subwindows
// Copyright:   (c) 2006, Ivan Laptev, TT Solutions
// License:     GPL, Please contact us for commercial license.
//              http://www.tt-solutions.com/
///////////////////////////////////////////////////////////////////////////////
#include "objectdet/prune_subwindows.h"

#include <algorithm>
#include <sstream>

struct CompareDfce
{
    bool operator () ( SubWindowInfo const & w1, SubWindowInfo const & w2 )
    {
        //return w1.dfce < w2.dfce;
        return w2.dfce < w1.dfce;
    }
};

inline
float get_overlapping_coef( SubWindowInfo const & w1, SubWindowInfo const & w2 )
{
	using namespace std;
    //int x = std::min(w1.x + w1.w, w2.x + w2.w) - std::max(w1.x, w2.x);
    int x = static_cast<int>(min(w1.x + w1.w, w2.x + w2.w))
	      - static_cast<int>(max(w1.x, w2.x));
    if (x > 0)
    {
        //int y = std::min(w1.y + w1.h, w2.y + w2.h) - std::max(w1.y, w2.y);
        int y = static_cast<int>(min(w1.y + w1.h, w2.y + w2.h))
			  - static_cast<int>(max(w1.y, w2.y));
        if (y > 0)
        {
            // unsigned int sx = std::max(w1.x + w1.w, w2.x + w2.w) - std::min(w1.x, w2.x) + 1;
            // unsigned int sy = std::max(w1.y + w1.h, w2.y + w2.h) - std::min(w1.y, w2.y) + 1;
            // same thing as above
            // +1 is simply to avoid division by zero
            size_t sx = w1.w + w2.w - x + 1;
            size_t sy = w1.h + w2.h - y + 1;

            return (float)(x * y) / (float)(sx * sy);
        }
    }
    return 0;
}

void PruneSubWindows( SubWindows const & good_windows,
                      double overlap_threshold,
                      size_t min_cluster_size,
                      SubWindows & window_clusters )
{
    if (good_windows.empty())
        return;

    SubWindows windows = good_windows;
    // sort subwindows by dfce (decreasing)
    std::sort( windows.begin(), windows.end(), CompareDfce() );

    typedef std::vector<SubWindowInfo*> WindowPtrs;

    WindowPtrs window_ptrs;
    // while performing pruning we will modify windows[i].passed to false
    // to indicate that the subwindow is disabled (already pruned or accepted)
    for (SubWindows::iterator wit = windows.begin(); wit != windows.end(); ++wit)
    if (wit->passed)
    {
        window_ptrs.clear();
        // find all the subwindows overlapping enough with this one
		for (SubWindows::iterator w2it = windows.begin(); w2it != windows.end(); ++w2it){
        //printf("new window ");
		if (w2it->passed)
        {
			//printf("passed ");
            float const coef = get_overlapping_coef( *wit, *w2it );
            if (coef >= overlap_threshold)
            {
                window_ptrs.push_back( &*w2it );
            }
		} //else {printf("not passed\n");}
		}

        if (!window_ptrs.empty() && window_ptrs.size() >= min_cluster_size)
        {
            size_t xsum = 0;
            size_t ysum = 0;
            size_t wsum = 0;
            size_t hsum = 0;
            // windows are of the same size, see a note above
            // unsigned int wsum;
            // unsigned int hsum;
            for (WindowPtrs::const_iterator cit = window_ptrs.begin();
                                            cit != window_ptrs.end(); ++cit)
            {
                xsum += (*cit)->x;
                ysum += (*cit)->y;
                wsum += (*cit)->w;
                hsum += (*cit)->h;
            }
            SubWindowInfo window_cluster = (*wit);
            window_cluster.x = xsum / window_ptrs.size();
            window_cluster.y = ysum / window_ptrs.size();
            window_cluster.w = wsum / window_ptrs.size();
            window_cluster.h = hsum / window_ptrs.size();
            window_cluster.cluster_size = window_ptrs.size();

            // now remove any subwindow near that resulting cluster
            for (SubWindows::iterator w2it = windows.begin(); w2it != windows.end(); ++w2it)
            if (w2it->passed)
            {
                float const coef = get_overlapping_coef( window_cluster, *w2it );
                if (coef >= overlap_threshold)
                {
                    w2it->passed = false;
                }
            }

            window_clusters.push_back( window_cluster );
        }
    }
}
